package firstday.Test2;

import java.util.ArrayList;

public class LoopHeadDILinkedList <T>{
    protected DNode<T> head; //不带数据的头结点
    //构造函数
    public LoopHeadDILinkedList(){
        this.head = new DNode<>();//初始化头结点
        //让头和尾连接形成一个空链表
        this.head.next=head;
        this.head.prev=head;
    }
//1、传入一个数组转换为链表
    public LoopHeadDILinkedList(T[] array)
    {
        this();
        if (array!=null && array.length>0)
        {
            DNode<T> p= new DNode<>(array[0]);
            head.next=p;
            head.prev=p;
            p.prev=head;
            p.next=head;
            int i=1;
            while (i<array.length)
            {
                p.next=new DNode<>(array[i++],p,head);
                head.prev=p.next;
                p=p.next;
            }
        }
    }
//2、判断循环双链表是否为空
    public boolean isEmpty() {
        //循环双链表的后继指针指向自己说明是空链表
        return this.head.next==head;
    }
//3、返回链表的长度
    public int length() {
        int length=0;
        DNode<T> p=this.head.next;
        while (p!=this.head){
            length++;
            p=p.next;
        }
        return length;
    }
//4、获取指定索引的节点
    public T get(int index) {
        if (index>=0)
        {
            int j=0;
            DNode<T> p=this.head.next;
            while (p!=head && j<index)
            {
                j++;
                p=p.next;
            }
            if (p!=head)
                return p.data;
        }
        return null;
    }
//5、根据指定索引替换节点data的值，结果返回被替换的data
    public T set(int index, T data) {
        if (data==null){
            return null;
        }
        if(index>=0){
            int j=0;
            DNode<T> p=this.head.next;

            while (p!=head&&j<index){
                j++;
                p=p.next;
            }
            //如果不是头结点
            if(p!=head){
                T old = p.data;
                p.data=data;
                return old;
            }
        }
        return null;
    }
//6、根据指定索引位置，向链表添加数据data
    public boolean add(int index, T data) {
        int size=length();
        if(data==null||index<0||index>=size)
            return false;
        DNode<T> p=this.head;
        //寻找插入点的位置
        int j=0;
        while (p.next!=head&&j<index){
            p=p.next;
            j++;
        }
        //创建新结点,如果index=3,那么插入的位置就是第4个位置
        DNode<T> q=new DNode<>(data,p,p.next);
        p.next=q;
        p.next.prev=q;
        return true;
    }
//7、在链表尾部添加数据
    public boolean add(T data) {
        if(data==null)
            return false;
        //创建新结点,让前继指针指向head.pre,后继指针指向head
        DNode<T> p=new DNode<>(data,head.prev,head);
        //更新tail后继指针的指向
        this.head.prev.next=p;
        this.head.prev=p;
        return true;
    }
//8、删除指定索引位置的元素
    public T remove(int index) {
        T old = null;
        int size=length();
        if (index<0||index>=size)
            return old;
        int j=0;
        DNode<T> p=this.head.next;//p指向第一个元素
        while (p!=head && j<index)
        {
            j++;
            p = p.next;
        }
        if (p!=head)
        {
            old = p.data;
            p.prev.next = p.next;
            p.next.prev = p.prev;
        }
        return old;//返回被删除的元素
    }
//9、清除链表全部元素
    public void clear() {
        this.head.prev = head;
        this.head.next = head;
    }
    @Override
    public String toString()
    {
        String str="(";
        DNode<T> p = this.head.next;
        while (p!=head)
        {
            str += p.data.toString();
            p = p.next;
            if (p!=head)
                str += ", ";
        }
        return str+")";
    }
    public static void main(String[] args){
        String[] letters={"A","B","C","D","Z","E","F","Z"};
        LoopHeadDILinkedList<String> list=new LoopHeadDILinkedList<>(letters);
        System.out.println("init list-->"+list.toString());
        System.out.println("list.get(3)->"+list.get(3));
        System.out.println("list:"+list.toString());
        System.out.println("list.add(4,Y)—>"+list.add(4,"Y"));
        System.out.println("list:"+list.toString());
        System.out.println("list.add(Z)—>"+list.add("Z"));
        System.out.println("list:"+list.toString());
        System.out.println("list.set(4,P)-->"+list.set(4,"P"));
        System.out.println("list:"+list.toString());
        System.out.println("list.remove(3)-->"+list.remove(3));
        System.out.println("list:"+list.toString());
        list.clear();
        System.out.println("list.clear()"+list.toString());

        //查看ArrayList源码
        ArrayList list1=new ArrayList();
    }
}
//ArrayList和LinkedList的区别

//ArrayList 是以动态数组的形式存储数据，
//在数组临界点 需要扩容数组时，每次扩容会扩大上次容量的一半
//默认储存10个数据，    private static final int DEFAULT_CAPACITY = 10;
// 超过10个数据时，int newCapacity = oldCapacity + (oldCapacity >> 1);原来的长度+原来长度右移一位
//由于数组的连续性，所以arraylist的查询速度很快，但在指定位置（非首尾）插入时，影响其他数据索引。
//相比较linkedList插入慢。 即查快改慢。

//LinkedList 是以双向链表的形式存储数据。
//个人理解: 双向链表就是一个数据 具有两个指针，一个指向上一个元素，一个指向下一个元素。
//占内存多，每个节点都需要开辟一个头指针和一个未指针内存
//在查询时，LinkedList需要遍历整个链表且不能像数组一样通过下表查询，所以速度没有arrayList快。
//但是在指定位置插入数据时，只需要知道上一个位置的索引和下一个位置的索引就可以执行插入操作了。
//即对比arrayList 查慢 改快。